#include <stdio.h>				// for use of printf, scanf 
#include <malloc.h>				// for use of malloc 
#include <time.h>				// for use of time 
#include <malloc.h>				// for use of malloc, free 
#include <ctype.h>  			// for use of toupper 
#include <stdlib.h>				// for use of srand, rand
#include <string.h>				// for use of strcmp, strcpy 

#define Max_Tree 10				// Maximum list size 
#define Max_Length 50			// Maximum string size
	
typedef struct node *tree_ptr;
typedef struct node				// Declare ch_node type
{
	tree_ptr llink;
	int data;
	tree_ptr rlink;
};

tree_ptr btree = NULL;

struct string						// Declare struct named string
{
	char name[Max_Length];			// Name of string
	tree_ptr ptr;				 	// Root pointer of tree
};

struct string Tree[Max_Tree];		// Declare string named Tree 

void DisplayMenu(void);
void DisplayGoodbye(void);
void Initialize(char* input);
void Insert_Tree(void);
void Make_Tree(char* input, int flag);
void insert_node(tree_ptr node, int key);
void Inorder_Tree(void);
void inOrder(tree_ptr node);
void Preorder_Tree(void);
void preOrder(tree_ptr node);
void Postorder_Tree(void);
void postOrder(tree_ptr node);
void Levelorder_Tree(void);
void levelOrder(tree_ptr node);
void Copy_Tree(void);
void Equal_Tree(void);
void Search_Tree(void);
void Height_Tree(void);
void Delete_Tree(void);
void delete(tree_ptr node, int key);

int count = 0;
int empty_tree = -1;
int Square(int number);
int Char_to_Int(input);
int Check_Input(char* input);
int equalBST(tree_ptr node1, tree_ptr node2);
int treeHeight(tree_ptr node);
int Find_Height(tree_ptr node, int curHeight, int Curmax);

tree_ptr search(tree_ptr node, int key);
tree_ptr modified_search(tree_ptr node, int key);
tree_ptr copyBST(tree_ptr node);

main()
{
	DisplayMenu();				// Major function
	DisplayGoodbye();			// Print out goodbye message

	return (EXIT_SUCCESS);
}

void DisplayMenu(void)	// Major function. Print out main menu
{
	int i;
	int flag = 1;
	char choice[Max_Length];

	for(i=0; i<Max_Tree; i++)	// Initialize
		Tree[i].ptr = NULL;

	while(flag)	// Loop
	{
		Initialize(choice);	// Initialize

		printf("(1)Insert  (2)Search    (3)Delete      (4)Height (5)Preorder \n" 
			"(6)Inorder (7)Postorder (8)Level Order (9)Copy   (0)Equal (x)Exit Choice? ");

		fflush(stdin);				// Buffer clear
		scanf("%s", choice);

		if( choice[1] != '\0' )		// If input is wrong then retry
		{
			printf("Wrong input. Please retry!\n\n");
			continue;
		}
		
		switch( toupper(choice[0]) )	// If choice[0] is small letter then covert to big letter
		{
			case '1':
				Insert_Tree();		// Insert
				break;
			case '2':
				Search_Tree();		// Search
				break;
			case '3' :
				Delete_Tree();		// Delete
				break;
			case '4':
				Height_Tree();		// Height
				break;
			case '5':
				Preorder_Tree();	// Preorder
				break;
			case '6':
				Inorder_Tree();		// Inorder
				break;
			case '7':
				Postorder_Tree();	// Postorder
				break;
			case '8':
				Levelorder_Tree();	// Levelorder
				break;
			case '9':
				Copy_Tree();		// Copy
				break;
			case '0':
				Equal_Tree();		// Equal
				break;
			case 'X':			// Program out
				flag = 0;
				break;
			default:			// If choice is wrong then retry.
				printf("Iligal choice. Try again!\n\n");
				break;
		}
	}
}

void DisplayGoodbye(void)	// Print out goodbye message
{
	printf("Thank you for using this software!\n");
}

void Initialize(char* input)	// Initialize
{
	int i;

	for(i=0; i<Max_Length; i++)
		input[i] = '\0';
}

void Make_Tree(char* input, int flag)	// Convert input into each integer number and call insert_node()
{
	int i, j, k;
	int counter=0, sum=0;

	for(i=0; i<Max_Length; i++)
	{
		k = i - 1;

		if( input[i] == 32 || input[i] == '\0' )	// If input[i] is ' ' or '\0' then convert and insert
		{
			for(j=0; j<counter; j++)
			{
				sum = sum + Char_to_Int(input[k]) * Square(j);	// Convert
				k = k - 1;
			}
		
			insert_node(Tree[flag].ptr, sum);	// Call insert_node()

			sum = 0;	// Initialize
			counter = 0;	// Initialize
		}
		else
			counter++;	// Increase counter

		if( input[i] == '\0' )
			break;
	} 
}

void Insert_Tree(void)	// Insert
{
	int i;
	char name[Max_Length], input[Max_Length];

	while(1)
	{
		Initialize(name);	// Initialize

		printf("Type the name of BST: ");
		fflush(stdin);
		scanf("%s", name);

		if( count == Max_Tree-1 )	// If array of BST is full then does not create
		{
			printf("Do not create more BST!\n\n");
			return;
		}

		for(i=0; i<Max_Tree; i++)	// If tree has the same name does exist
		{
			if( strcmp(name, Tree[i].name) == 0 )
				break;
		}

		if( i == Max_Tree && count == Max_Tree-1 )	// If array of BST is full
		{
			printf("Do not create more BST!\n");
			return;
		}
		else
			break;
	}

	while(1)
	{
		Initialize(input);	// Initialize

		printf("Type numbers to input: ");
		fflush(stdin);
		fgets(input, sizeof(input), stdin);

		for(i=0; i<Max_Length; i++)
		{
			if( input[i] == 10 )	// If input[i] is 'enter' then convert into '\0'
			{
				input[i] = '\0';
				break;
			}
		}

		if( !Check_Input(input) )	// If input is wrong
			continue; 		// Retry

		for(i=0; i<Max_Tree; i++)	
		{
			if( strcmp(name, Tree[i].name) == 0 )	// If tree has the same name does exist
				break;
		}

		if( i == Max_Tree )	// If tree has the same name does not exist
		{
			strcpy(Tree[count].name, name);
			Make_Tree(input, count);	// Call Make_tree()
			printf("%s inserted into %s\n\n", input, name);
			count++;	// Increase count
			break;
		}
		else if( Tree[i].ptr == NULL )	// If tree has the same name does exist but has not any node
		{
			empty_tree = i;
			Make_Tree(input, i);	// Call Make_tree()
			printf("%s inserted into %s\n\n", input, name);
			break;
		}				
		else 	// If tree has the same name does exist and has any node
		{
			Make_Tree(input, i);	// Call Make_tree()
			printf("%s inserted into %s\n\n", input, name); 
			break;
		} 
	}
}

void insert_node(tree_ptr node, int key)	// Insert new node into the tree
{
	tree_ptr temp;

	btree = modified_search(node, key);	// Search the parent node of new node

	if( search(node, key) == NULL )		// If key has the same value does not exist
	{
		temp = (tree_ptr)malloc(sizeof(struct node));	// Memory allocation

		if( temp == NULL )
		{
			fprintf(stderr, "The memory is full.\n");
			exit(1);
		}

		temp->data = key;
		temp->llink = temp->rlink = NULL;

		if( node != NULL )	// If tree has has any node
		{
			if( key < btree->data )		// If key of new node is smaller than key of parent node
				btree->llink = temp;	// Left link of parent node point to temporary node
			else
				btree->rlink = temp;	// Right link of parent node point to temporary node
		}
		else if( empty_tree != -1 )	// If name of tree does exist but has not any node
		{
			Tree[empty_tree].ptr = temp;	// Starting pointer of tree point to temporary node
			empty_tree = -1;	// Initialize empty_tree
		}
		else	// If node is starting pointer of new tree
			Tree[count].ptr = temp;		// Starting pointer of tree point to temporary node
	}

	btree = NULL;	// Initialize btree
}

void inOrder(tree_ptr node)	// Type of inorder 
{
	if( node )
	{
		inOrder(node->llink);
		printf("%d ", node->data);
		inOrder(node->rlink);
	}
}

void Inorder_Tree(void)		// Inorder
{
	int i;
	char name[Max_Length];

	while(1)
	{
		Initialize(name);	// Initialize

		printf("Type the name of BST: ");
		scanf("%s", name);

		for(i=0; i<Max_Tree; i++)
		{
			if( strcmp(name, Tree[i].name) == 0 )
				break;
		}

		if( i == Max_Tree )	// If tree does not exist
		{
			printf("%s does not exist. Please retry!\n", name);
			continue;
		}
		else if( Tree[i].ptr == NULL )	// If tree has not any node
		{
			printf("%s does not have any node!\n\n", name);
			break;
		}
		else	
		{
			printf("Inorder traversal!\n");
			inOrder(Tree[i].ptr);	// Call inOrder()
			printf("\n\n");
			break;
		}
	}
}

void preOrder(tree_ptr node)	// Type of preorder
{
	if( node )
	{
		printf("%d ", node->data);
		preOrder(node->llink);
		preOrder(node->rlink);
	}
}

void Preorder_Tree(void)	// Preorder
{
	int i;
	char name[Max_Length];

	while(1)
	{
		Initialize(name);	// Initialize

		printf("Type the name of BST: ");
		scanf("%s", name);

		for(i=0; i<Max_Tree; i++)
		{
			if( strcmp(name, Tree[i].name) == 0 )
				break;
		}

		if( i == Max_Tree )	// If tree does not exist
		{
			printf("%s does not exist. Please retry!\n", name);
			continue;
		}
		else if( Tree[i].ptr == NULL )	// If tree has not any node
		{
			printf("%s does not have any node!\n\n", name);
			break;
		}
		else
		{
			printf("Inorder traversal!\n");
			preOrder(Tree[i].ptr);	// Call preOrder()
			printf("\n\n");
			break;
		}
	}
}

void postOrder(tree_ptr node)	// Type of postorder
{
	if( node )
	{
		postOrder(node->llink);
		postOrder(node->rlink);
		printf("%d ", node->data);
	}
}

void Postorder_Tree(void)	// Postorder
{
	int i;
	char name[Max_Length];

	while(1)
	{
		Initialize(name);	// Initialize

		printf("Type the name of BST: ");
		scanf("%s", name);

		for(i=0; i<Max_Tree; i++)
		{
			if( strcmp(name, Tree[i].name) == 0 )
				break;
		}

		if( i == Max_Tree )	// If tree does not exist
		{
			printf("%s does not exist. Please retry!\n", name);
			continue;
		}
		else if( Tree[i].ptr == NULL )	// If tree has not any node
		{
			printf("%s does not have any node!\n\n", name);
			break;
		}
		else
		{
			printf("Inorder traversal!\n");
			postOrder(Tree[i].ptr);	// Call postOrder()
			printf("\n\n");
			break;
		}
	}
}


void levelOrder(tree_ptr node)	// Type of levelorder
{
	int i;
	int front = 0, rear = 0;
	tree_ptr queue[Max_Length];

	for(i=0; i<Max_Length; i++)
		queue[i] = NULL;

	if( !node )	// If tree has not any node
		return;	// Return

	queue[rear] = node;	// Push
	rear++;		// Increase rear

	while(1)
	{
		node = queue[front];	// Pop
		front++;	// Increase front

		if( node )	// If node does exist
		{
			printf("%d ", node->data);	
			
			if( node->llink )	// If left link of node is not null
			{
				queue[rear] = node->llink;	// Push
				rear++;		// Increase rear
			}
			if( node->rlink )	// If right linf of node is not null
			{
				queue[rear] = node->rlink;	// Push
				rear++;		// Increaes rear
			}
			
		}
		else 
			break;
	}
}

void Levelorder_Tree(void)	// Levelorder
{
	int i;
	char name[Max_Length];

	while(1)
	{
		Initialize(name);	// Initialize

		printf("Type the name of BST: ");
		scanf("%s", name);

		for(i=0; i<Max_Tree; i++)
		{
			if( strcmp(name, Tree[i].name) == 0 )
				break;
		}

		if( i == Max_Tree )	// If tree does not exist
		{
			printf("%s does not exist. Please retry!\n", name);
			continue;
		}
		else if( Tree[i].ptr == NULL )	// If tree has not any node
		{
			printf("%s does not have any node!\n\n", name);
			break;
		}
		else
		{
			printf("Levelorder traversal!\n");
			levelOrder(Tree[i].ptr);	// Call levelOrder()
			printf("\n\n");
			break;
		}
	}
}

void Copy_Tree(void)	// Copy
{
	int i, j;
	char name1[Max_Length], name2[Max_Length];

	tree_ptr temp;

	while(1)
	{
		Initialize(name1);	// Initialize

		printf("Type the name of original and new BST: ");
		scanf("%s %s", name1, name2);

		for(i=0; i<Max_Tree; i++)
		{
			if( strcmp(name1, Tree[i].name) == 0 )
				break;
		}

		if( i == Max_Tree )	// If tree does not exist
		{
			printf("%s does not exist. Please retry!\n", name1);
			continue;
		}
		else
		{
			for(j=0; j<Max_Tree; j++)
			{
				if( strcmp(name2, Tree[j].name) == 0 )
					break;
			}

			if( j != Max_Tree )	// If tree does not exist
			{
				printf("%s exist. Please retry!\n", name2);
				continue;
			}
			else	// Copy
			{
				temp = (tree_ptr)malloc(sizeof(struct node));	// Memory allocation
				temp = copyBST(Tree[i].ptr);	// Call copyBST()
				strcpy(Tree[count].name, name2);
				Tree[count].ptr = temp;		// Starting pointer of new tree point to temporary node
				count++;	// Increase count
				printf("%s is copied from %s!\n\n", name2, name1);
				break;
			}
		}

	}
}

void Equal_Tree(void)	// Equal
{
	int i, j;
	char name1[Max_Length], name2[Max_Length];

	while(1)
	{
		Initialize(name1);	// Initialize
		Initialize(name2);	// Initialize

		printf("Type two BSTs to compare: ");
		scanf("%s %s", name1, name2);

		for(i=0; i<Max_Tree; i++)
		{
			if( strcmp(name1, Tree[i].name) == 0 )
				break;
		}

		if( i == Max_Tree )	// If tree does not exist
		{
			printf("%s does not exist. Please retry!\n", name1);
			continue;
		}
		else
		{
			for(j=0; j<Max_Tree; j++)
			{
				if( strcmp(name2, Tree[j].name) == 0 )
					break;
			}

			if( j == Max_Tree )	// If tree does not exist
			{
				printf("%s does not exist. Please retry!\n", name2);
				continue;
			}
			else
			{
				if( equalBST(Tree[i].ptr, Tree[j].ptr) == 1 )	// If two tree is equal
				{
					printf("%s and %s are equal!\n\n", name1, name2);
					break;
				}
				else	// If two tree is not equal
				{
					printf("%s and %s are not equal!\n\n", name1, name2);
					break;
				} 
			}
		}
	}
}

void Search_Tree(void)	// Search
{
	int i, j, k, l;
	int sum=0, counter=0;
	char name[Max_Length], input[Max_Length];

	tree_ptr temp;

	while(1)
	{
		Initialize(name);	// Initialize

		printf("Type the name of BST: ");
		fflush(stdin);
		scanf("%s", name);

		for(i=0; i<Max_Tree; i++)
		{
			if( strcmp(name, Tree[i].name) == 0 )
				break;
		}

		if( i == Max_Tree )	// If tree does not exist
		{
			printf("%s does not exist. Please retry!\n", name);
			continue;
		}
		else 
			break;
	}

	while(1)
	{
		Initialize(input);	// Initialize

		printf("Type a number to search: ");
		fflush(stdin);
		fgets(input, sizeof(input), stdin);

		for(j=0; j<Max_Length; j++)
		{
			if( input[j] == 10 )
			{
				input[j] = '\0';
				break;
			}
		}

		if( !Check_Input(input) )	// If input is wrong then retry
			continue; 

		for(l=0; l<Max_Length; l++)
		{
			k = l - 1;

			if( input[l] == '\0' )
			{
				for(j=0; j<counter; j++)
				{
					sum = sum + Char_to_Int(input[k]) * Square(j);	// Convert
					k = k - 1;
				}
			
				temp = search(Tree[i].ptr, sum);	// Call search()

				if( temp != NULL )	// If key does exist in tree
				{
					printf("%d exist in %s!\n\n", sum, name);
					break;
				}
				else	// If key does not exist in tree
				{
					printf("%d does not exist in %s\n\n", sum, name);
					break;
				}
			}
			else
				counter++;	// Increase counter
		}

		break;
	}
}
	
void Height_Tree(void)	// Height
{
	int i;
	char name[Max_Length];

	while(1)
	{
		Initialize(name);	// Initialize

		printf("Type the name of BST: ");
		scanf("%s", name);

		for(i=0; i<Max_Tree; i++)
		{
			if( strcmp(name, Tree[i].name) == 0 )
				break;
		}

		if( i == Max_Tree )	// If tree does not exist
		{
			printf("%s does not exist. Please retry!\n", name);
			continue;
		}
		else
		{
			if( Tree[i].ptr == NULL )	// If tree does not has any node
			{
				printf("%s does not have any node.\n\n", name);
				break;
			}
			else	// Print out 
			{
				printf("Height of the %s: %d!\n\n", name, treeHeight(Tree[i].ptr)+1);
				break;
			}
		}
	}
}

void Delete_Tree(void)	// Delete
{
	int i, j, k, l;
	int sum=0, counter=0;
	char name[Max_Length], input[Max_Length];

	tree_ptr temp;

	while(1)
	{
		Initialize(name);	// Initialize

		printf("Type the name of BST: ");
		fflush(stdin);
		scanf("%s", name);

		for(i=0; i<Max_Tree; i++)
		{
			if( strcmp(name, Tree[i].name) == 0 )
				break;
		}

		if( i == Max_Tree )	// If tree does not exist
		{
			printf("%s does not exist. Please retry!\n", name);
			continue;
		}
		else 
			break;
	}

	while(1)
	{
		Initialize(input);	// Initialize

		printf("Type a number to search: ");
		fflush(stdin);
		fgets(input, sizeof(input), stdin);

		for(j=0; j<Max_Length; j++)
		{
			if( input[j] == 10 )
			{
				input[j] = '\0';
				break;
			}
		}

		if( !Check_Input(input) )	// If input is wrong then retry
			continue; 

		for(l=0; l<Max_Length; l++)
		{
			k = l - 1;

			if( input[l] == '\0' )
			{
				for(j=0; j<counter; j++)
				{
					sum = sum + Char_to_Int(input[k]) * Square(j);	// Convert
					k = k - 1;
				}
			
				temp = search(Tree[i].ptr, sum);

				if( temp != NULL )	// If node has the key does exist 
				{
					delete(Tree[i].ptr, sum);	// Call delete()
					printf("%d deleted from %s!\n\n", sum, name);
					break;
				}	
				else	// If node has the key does not exist
				{
					printf("%d does not exist in %s\n\n", sum, name);
					break;
				}
			}
			else
				counter++;	// Increase counter
		}

		break;
	}
}

void delete(tree_ptr node, int key)	// delete node 
{
	int i;
	tree_ptr parent, child, temp;

	for(i=0; i<Max_Tree; i++)
	{
		if( Tree[i].ptr == node )
			break;
	}
		
	parent = NULL;	
	temp = node;

	while( temp != NULL && temp->data != key )	// Search for node and parent of node
	{
		parent = temp;
		
		if( key < temp->data )
			temp = temp->llink;
		else
			temp = temp->rlink;
	}

	// No child
	if( temp->llink == NULL && temp->rlink == NULL )
	{
		if( parent != NULL )
		{
			if( parent->llink = temp )	
				parent->llink = NULL;
			else
				parent->rlink = NULL;
		}
		else
			Tree[i].ptr = NULL;
	}
	// One child
	else if( temp->llink == NULL || temp->rlink == NULL )
	{
		if( temp->llink != NULL )
			child = temp->llink;
		else
			child = temp->rlink;

		if( parent != NULL )
		{
			if( parent->llink == temp )
				parent->llink = child;
			else
				parent->rlink = child;
		}
		else 
		{
			node = child;
			Tree[i].ptr = child;
		}
	}
	// Two childs
	else
	{
		parent = temp;
		child = temp->rlink;

		while(child->llink != NULL)
		{
			parent = child;
			child = child->llink;
		}
		
		if( parent->llink == child )
			parent->llink = child->rlink;
		else
			parent->rlink = child->rlink;

		temp->data = child->data;
		temp = child;
	}

	free(temp);
}

int Square(int number)	// Square
{
	int i, sum=1;

	if( number == 0 )	// If number is zero
		return 1;	// Return 10^0
	else
	{
		for(i=0; i<number; i++)	
			sum = sum * 10;		// sum = 10^i
	}
	
	return sum;	// Return 10^number
}			

int Char_to_Int(char input)	// Convert character type into integer type
{
	return input-'0';
}

int Check_Input(char* input)	// Check the input
{
	int i;

	for(i=0; i<Max_Length; i++)
	{
		if( input[i] == '\0' )
			return 1;
		else if( (input[i] < 48 || input[i] > 57) && input[i] != 32 )	// If input[i] is not '0' to '9' and ' '
		{
			printf("%c is wrong input. Please retry!\n", input[i]);
			return 0;
		}
	} 

	return 0; 
}

int equalBST(tree_ptr node1, tree_ptr node2)	// equalBST
{
	return ((!node1 && !node2) || (node1 && node2) && (node1->data == node2->data) && 
		equalBST(node1->llink, node2->llink) && equalBST(node1->rlink, node2->rlink)); 
}

int treeHeight(tree_ptr node)	// treeHeight
{
	int curHeight =0, curMax = 0;
	return Find_Height(node, curHeight, curMax);
}

int Find_Height(tree_ptr node, int curHeight, int curMax)	// Find_Height
{
	if( node != NULL )
	{
		if( curHeight > curMax )
			curMax = curHeight;
		if( node->llink != NULL )
			curMax = Find_Height(node->llink, curHeight+1, curMax);
		if( node->rlink != NULL )
			curMax = Find_Height(node->rlink, curHeight+1, curMax);
	}
	
	return curMax;	// Return curMax
}

tree_ptr search(tree_ptr node, int key)		// Search
{
	if( !node )	// If node is null
		return NULL;	// Return null
	else if( key == node->data )	// If key does exist  
		return node;	// Return node
	else if( key < node->data )	// If key is smaller than data of node
		return search(node->llink, key);	// Search the left BST for key

	return search(node->rlink, key);	// If key is greater than data of node then search the right BST for key
}

tree_ptr modified_search(tree_ptr node, int key)	// Search for parent node of new node
{
	tree_ptr temp;

	if( !node )	// If node is null
		return NULL;	// Return null
	
	temp = node;

	if( key < temp->data )	// If key is smaller than data of node
	{
		if( temp->llink == NULL )	// If left link of node is null
			return temp;	// Return temporary node
		else	// If left link of node is not null
			return modified_search(temp->llink, key); // Modified search to left BST
	}
	else if( key > temp->data )	// If key is greater than data of node
	{
		if( temp->rlink == NULL )	// If right link of node is null
			return temp;	// Return temporary node
		else	// If right link of node is not null
			return modified_search(temp->rlink, key); // Modified search to right BST
	}

	return NULL;
}

tree_ptr copyBST(tree_ptr node)	// copyBST
{
	tree_ptr temp;

	if( node )	// If node is not null then copy
	{
		temp = (tree_ptr)malloc(sizeof(struct node));	// Memory allocation

		if( temp == NULL )
			exit(1);

		temp->llink = copyBST(node->llink);	
		temp->rlink = copyBST(node->rlink);

		temp->data = node->data;

		return temp;
	}

	return NULL;
}